import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: YKH
 * Date: 2022-07-18
 * Time: 21:39
 */
class TreeNode {
      int val = 0;
      TreeNode left = null;
      TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}

 class ListNode {
    int val;
    ListNode next = null;
 }
public class Practise {
    /**
     * 合并二叉树
     * 已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，
     * 否则空的位置就由另一个树的结点来代替。例如：
     *
     * @param t1
     * @param t2
     * @return
     */
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        // write code here
        if (t1 == null)
            return t2;
        if (t2 == null)
            return t1;
        TreeNode root = new TreeNode(t1.val + t2.val);
        root.left = mergeTrees(t1.left, t2.left);
        root.right = mergeTrees(t1.right, t2.right);
        return root;
    }

    /**
     * 二叉树镜像
     * 操作给定的二叉树，将其变换为源二叉树的镜像。
     * 数据范围：二叉树的节点数 0 \le n \le 10000≤n≤1000 ， 二叉树每个节点的值 0\le val \le 10000≤val≤1000
     * 要求： 空间复杂度 O(n)O(n) 。本题也有原地操作，即空间复杂度 O(1)O(1) 的解法，时间复杂度 O(n)O(n)
     * <p>
     * 比如：
     * 源二叉树
     *
     * @param pRoot
     * @return
     */
    public TreeNode Mirror(TreeNode pRoot) {
        // write code here
        if (pRoot == null) return null;
        TreeNode left = Mirror(pRoot.left);
        TreeNode right = Mirror(pRoot.right);
        TreeNode temp = left;
        pRoot.left = right;
        pRoot.right = temp;
        return pRoot;
    }

    /**
     * 链表的指定区间翻转
     *
     * @param head
     * @param m
     * @param n
     * @return
     */


    public ListNode reverseBetween(ListNode head, int m, int n) {
        //m = n 时 ,不需要翻转, 直接返回原来的链表即可
        if (m == n) {
            return head;
        }
        // write code here
        ListNode cur = head;
        ListNode prev = null;
        ListNode ps = null;     //记录开始位置的前一个位置
        ListNode star = null;  //记录开始翻转的位置
        ListNode pe = null;     //记录翻转结束位置的后一个位置
        ListNode end = null;   //记录结束的位置
        int count = 0;
        //找到翻转区间的起点和结束位置,以及前后位置
        while (cur != null) {
            count++;
            if (count == m) {
                ps = prev;
                star = cur;
            }
            if (count == n) {
                pe = cur.next;
                end = cur;
                break;
            }
            prev = cur;
            cur = cur.next;
        }
        //进行链表翻转
        ListNode ret = reserve(star, end, ps, pe);
        //当os为空说明头结点被翻转了,返回翻转后的结果 , 不为空连接翻转后的连边, 返回原来的头结点
        if (ps != null) {
            ps.next = ret;
            return head;
        } else {
            return ret;
        }
    }

    //翻转区间链表
    public static ListNode reserve(ListNode star, ListNode end, ListNode ps, ListNode pe) {
        ListNode cur = star;
        ListNode prev = pe;
        while (cur != pe) {
            ListNode tmp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = tmp;
        }
        return prev;
    }

    /**
     * 链表的区间翻转
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        //找到每次翻转的尾部
        ListNode tail = head;
        //遍历k次到尾部
        for (int i = 0; i < k; i++) {
            //如果不足k到了链表尾，直接返回，不翻转
            if (tail == null)
                return head;
            tail = tail.next;
        }
        //翻转时需要的前序和当前节点
        ListNode pre = null;
        ListNode cur = head;
        //在到达当前段尾节点前
        while (cur != tail) {
            //翻转
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        //当前尾指向下一段要翻转的链表
        head.next = reverseKGroup(tail, k);
        return pre;
    }

    /**
     * 截断句子
     * 给你一个句子 s和一个整数 k ，请你将 s​​ 截断 s 使截断后的句子仅含 前 k 个单词。返回 截断 后得到的句子。
     */
    public String truncateSentence(String s, int k) {
        if (k == s.length()) return s;
        StringBuffer s2 = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == ' ') {
                k--;
                if (k == 0) {
                    break;
                }
            }
            s2.append(ch);
        }
        return s2.toString();
    }

    /**
     * 删除有序数组中的重复项
     * 给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
     * <p>
     * 由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么nums的前 k 个元素应该保存最终结果。
     * <p>
     * 将最终结果插入nums 的前 k 个位置后返回 k 。
     * <p>
     * 不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
     * <p>
     * 思路 : 升序数组, 相同的元素都相邻, 从前往后遍历数组, 相邻元素不同时, 进行覆盖即可.
     *
     * @param nums
     * @return
     */

    public int removeDuplicates(int[] nums) {
        int k = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                nums[k++] = nums[i];
            }
        }
        return k;
    }

    /** 罗马数字转整数
     * 字符          数值
     * I             1
     * V             5
     * X             10
     * L             50
     * C             100
     * D             500
     * M             1000
     *
     * 例如， 罗马数字 2 写做II，即为两个并列的 1 。12 写做XII，即为X+II。 27 写做XXVII, 即为XX+V+II。
     *
     * 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做IIII，而是IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
     *
     * 给定一个罗马数字，将其转换成整数。
     *

     * 链接：https://leetcode.cn/problems/roman-to-integer
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * 思路 : 当左边的数字比右边的数字进行比较 , 比起小时做减法, 否则做加法,到最后一位时,直接做加法即可
     */

    public int romanToInt(String s) {
        Map< Integer,Integer> map = new HashMap<>();
        int sum = 0;
        int prev = getValue(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            int cur = getValue(s.charAt(i));
            if (prev < cur) {
                sum -= prev;
            } else {
                sum += prev;
            }
            prev = cur;
        }
        sum += prev;
        return sum;
    }

    public int getValue(char ch) {
        switch (ch) {
            case 'I':
                return 1;
            case 'V':
                return 5;
            case 'X':
                return 10;
            case 'L':
                return 50;
            case 'C':
                return 100;
            case 'D':
                return 500;
            case 'M':
                return 1000;
            default:
                return 0;
        }
    }

    /**
     * 最后一块石头的重量
     * @param stones
     * @return
     */
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
        for( int i=0; i<stones.length; i++) {
            queue.offer( stones[i]);
        }
        int x, y;
        while(queue.size() > 1) {
            x = queue.poll();
            y = queue.poll();
            if( x != y) {
                queue.offer(x-y);
            }
        }
        if( !queue.isEmpty()) {
            return queue.poll();
        } else {
            return 0;
        }
    }

    /**
     * 拼写单词
     *
     * 给你一份『词汇表』（字符串数组）words和一张『字母表』（字符串）chars。
     *
     * 假如你可以用chars中的『字母』（字符）拼写出 words中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。
     *
     * 注意：每次拼写（指拼写词汇表中的一个单词）时，chars 中的每个字母都只能用一次。
     *
     * 返回词汇表words中你掌握的所有单词的 长度之和。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/find-words-that-can-be-formed-by-characters
     *
     * 示例 1：
     *
     * 输入：words = ["cat","bt","hat","tree"], chars = "atach"
     * 输出：6
     * 解释：
     * 可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。
     * @param words
     * @param chars
     * @return
     */
    public int countCharacters(String[] words, String chars) {
        int sum = 0;
        for(int i=0; i<words.length; i++) {
            //哈希表存储 chars中的字母 和 对应字母的个数
            Map<Character, Integer> map = new HashMap<>();
            for( int k=0;k<chars.length();k++) {
                char ch1 = chars.charAt(k);
                if( map.get(ch1) == null) {
                    map.put(ch1,1);
                } else {
                    int val = map.get(ch1);
                    map.put(ch1,val+1);
                }
            }

            String tmp = words[i];
            int len = 0;
            int j = 0;
            for( j=0; j<tmp.length(); j++) {
                char ch2 = tmp.charAt(j);
                //当map中存在该字母 , 用map中字母组成单词, map中对应字母次数-1;为0时移去该字母
                if(  map.get(ch2) != null ) {
                    int val = map.get(ch2);
                    if( val == 1) {
                        map.remove(ch2);
                    } else {
                        map.put(ch2, val-1);
                    }
                    len++;
                } else {   //不存在跳出循环
                    break;
                }
            }
            //统计总次数
            if( j>=tmp.length()) {
                sum += len;
            }
        }

        Set<Integer> set = new HashSet<>();
        return sum;
    }

    /**
     * 一年中的第几天
     * 给你一个字符串 date ，按 YYYY-MM-DD 格式表示一个 现行公元纪年法 日期。返回该日期是当年的第几天。
     * @param date
     * @return
     */
    public static int dayOfYear(String date) {
            int []arr = { 0,31,28,31,30,31,30,31,31,30,31,30,31};
            int month = (date.charAt(5)-'0')*10 + (date.charAt(6)-'0');
            int day = (date.charAt(8)-'0')*10 + (date.charAt(9)-'0');
            int sum = 0;
            for( int i=1;i <= month-1;i++) {
                sum += arr[i];
            }
            sum += day;
            if( month >2) {
                int year = 0;
                for( int i=0 ;i<4;i++) {
                    year += (date.charAt(i)-'0')* (Math.pow(10,3-i));
                }
                if(( year%400==0) || (year%4==0 && year%100!=0) ) {
                    sum++;
                }
            }
            return sum;
        }

    /**
     * leetcode 1171. 从链表中删去总和值为零的连续节点
     * 给你一个链表的头节点head，请你编写代码，反复删去链表中由 总和值为 0 的连续节点组成的序列，直到不存在这样的序列为止。
     *
     * 删除完毕后，请你返回最终结果链表的头节点。

     * 你可以返回任何满足题目要求的答案。
     *
     * （注意，下面示例中的所有序列，都是对ListNode对象序列化的表示。）
     *示例 1：
     *
     * 输入：head = [1,2,-3,3,1]
     * 输出：[3,1]
     * 提示：答案 [1,2,1] 也是正确的。
     *
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    /**
     思路: step1: 先找到区间和为0的区间 -> 利用前缀和, 前缀和相等的值相等的节点说明,其中间节点的和为0
     step2: 先遍历一遍链表, 用哈希表存储每个节点的前缀和,当后面节点的前缀和前面节点的前缀和相等时,在哈希表中会自动覆盖前面的节点
     step3 : 再次遍历链表, 根据前缀和在哈希表中查找, 将 当前的节点的next指向对应相同前缀和在哈希表中存放节点的next,即可删除区间为0的节点.
     */
    class Solution {
        public ListNode removeZeroSumSublists(ListNode head) {
            if(head == null)  return null;
            Map<Integer,ListNode > map = new HashMap<>();
            //创建虚拟头结点,防止头结点被删除时, 返回后续的节点
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            //利用哈希表存储 每个节点的前缀和(包含当前节点)
            ListNode cur = dummy;
            int sum = 0;
            while( cur!=null) {
                sum += cur.val;
                //当后面节点的前缀和前面节点的前缀和相等时,在哈希表中会自动覆盖前面的节点
                map.put( sum, cur);
                cur = cur.next;
            }
            cur = dummy;
            sum = 0;
            //再根据前缀和,在哈希表中查找,删除和为0 的区间.
            while( cur!=null) {
                sum += cur.val;
                cur.next = map.get(sum).next;
                cur = cur.next;
            }
            return dummy.next;
        }
    }
}
